package com.chenken;

/**
 *	分治 
 *	最大连续子序列之和
 *  给定一个长度为n的整数序列，求它的最大连续子序列之和
 */
public class DivideAndConquer {

	public static Integer maxSequence(int[] nums) {
		if(nums == null || nums.length == 0) return 0;
		return maxSequence(nums,0,nums.length);
	}

	/**
	 * 求从begin到end的最大连续子序列之和
	 * 假设问题的解是S[i,j),那么问题的解有3种可能
	 * 1.[i,j)存在于[begin,mid)中
	 * 2.[i,j)存在于[mid,end)中
	 * 3.[i,j)一部分存在于[begin,mid)中,另一部分存在于[mid,end)中,[i,j) = [i,mid)+[mid,j)
	 * @param nums
	 * @param begin
	 * @param end
	 * @return
	 */
	private static Integer maxSequence(int[] nums, int begin, int end) {
		//	分到只有一个元素时，返回
		if(end-begin < 2) {
			return nums[begin];
		}
		int mid = (begin+end) >> 1;
		
		//	从mid-1往begin加
		int leftMax = Integer.MIN_VALUE;
		int leftSum = 0;
		for(int i = mid - 1;i >= begin;i--) {
			leftSum += nums[i];
			leftMax = Math.max(leftMax, leftSum);
		}
		//	从mid往end加
		int rightMax = Integer.MIN_VALUE;
		int rightSum = 0;
		for(int i = mid; i < end; i++) {
			rightSum += nums[i];
			rightMax = Math.max(rightMax, rightSum);
		}
		return Math.max(leftMax + rightMax,
					Math.max(
							maxSequence(nums,begin,mid),
							maxSequence(nums,mid,end)
							)
					);
	}
	
	public static void main(String[] args) {
		int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
		System.out.println(maxSequence(nums));
	}
}
